#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#include <sys/time.h>

using namespace std;

bool exist( vector< vector<char> >& board, int y, int x, string word, int i) 
{
    if (i == word.size()) return true;
    if (y<0 || x<0 || y == board.size() || x == board[y].size() ) return false;
    if (board[y][x] != word[i]) return false;
    char tmp = board[y][x];
    board[y][x] = 0;
    bool existret = ( exist(board, y, x+1, word, i+1)
        || exist(board, y, x-1, word, i+1)
        || exist(board, y+1, x, word, i+1)
        || exist(board, y-1, x, word, i+1) );
    board[y][x] = tmp;
    return existret;
}


bool exist(vector< vector<char> >& board, string word)
{
    for (int y=0; y<board.size(); y++) {
        for (int x=0; x<board[y].size(); x++) {
            if (exist(board, y, x, word, 0)) return true;
        }
    }
    return false;

}






int main(int argc,char *argv[])
{
  vector< vector<char> > board;
  vector<char> a;
  //a.push_back('c');
  a.push_back('a');
  a.push_back('a');

  board.push_back(a);

/*  vector<char> b;*/
  //b.push_back('c');
  //b.push_back('d');
  ////b.push_back('a');
  /*board.push_back(b);*/

/*  vector<char> c;*/
  //c.push_back('b');
  //c.push_back('c');
  //c.push_back('d');
  /*board.push_back(c);*/

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  string s("aaa");

  bool ret = exist(board,s);

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  cout <<"ret:"<<ret<<endl;



  return 0;
}
